In general, main memory typically represents a significant portion of the costs associated with computer systems. To reduce such costs, various memory system frameworks have been proposed in which data compression is employed to store all or a portion of the contents of main memory in compressed form, so as to effectively yield an increase in memory storage without actually increasing the size of memory. These memory systems are generally referred to herein as “compressed memory systems.”
Compressed memory systems may include a main memory that stores compressed data and a cache memory, for example, to store uncompressed data, where data requests are served by fetching requested data from the cache memory. A “hit” refers to a circumstance in which the requested data is accessed from uncompressed data in the cache memory, On the other hand, a “miss” refers to a circumstance in which the requested data is not stored in the cache, thereby requiring the requested data to be fetched from compressed data stored in the main memory.
A common problem with compressed memory systems is the performance latency associated with accessing compressed data. For example, in the event of a “miss”, the requested data must be fetched from the compressed data in the main memory, decompressed, and then stored in uncompressed form in the cache memory. One way of reducing this performance penalty is to implement a large cache memory that can store a large amount of uncompressed data lines separate from main memory. This method, although effective, is limited by practical reasons due to the high costs associated with large cache memory. In other conventional compressed memory systems, a portion of main memory is allocated as a cache memory region, where some subset of data lines are stored uncompressed in the allocated cache memory region. A limiting factor with this conventional technique is that a relatively large cache directory, which is needed to access and manage uncompressed data items stored in the cache memory, must be held on a processor chip or some other chip outside of main memory.
Another common problem with compressed memory systems is performance latency associated with “reorganization work” that is needed for data accesses to compressed memory. Reorganization work refers to the series of operations of moving data to and from the compressed and uncompressed memory regions, which must be performed after data accesses to compressed memory. For example, in the event of a “miss” as discussed above, the requested data must be fetched from compressed memory, decompressed, and then stored in the uncompressed memory region. In the event that data items in the compressed memory and the uncompressed memory are mutually exclusive, then certain data in the uncompressed memory region must also be fetched from the uncompressed memory region, compressed, and then stored in the compressed area. These reorganization processes are generally needed to maintain high hit rates in the main memory area. Reorganization work is generally undesirable because it utilizes memory resources and can delay completion of other memory operations.